package 分治回溯.N皇后;


public class NQueens {
    private static int size = 8;
    private static int count = 0;
    private static int[][]  board = new int[size][size];
    public static void main(String[] args) {
        nQueens(0);
    }

    private static void nQueens(int row) {
        if (row == size){
            count++;
            System.out.println("第"+count+"个解：");
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    System.out.print(board[i][j]+" ");
                }
                System.out.println();
            }
        }else {
            for (int col = 0; col < size; col++) {
                if (!isDanger(row,col)){
                    for (int c = 0; c < size; c++) {
                        board[row][c] = 0;
                    }
                    board[row][col] = 1;
                    nQueens(row + 1);
                }
            }

        }

    }

    private static boolean isDanger(int row, int col) {
        //正上方
        for (int r = row - 1; r >= 0; r--){
            if (board[r][col] == 1){
                return true;
            }
        }

        //左上方
        for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--,c--){
            if (board[r][c] == 1){
                return true;
            }
        }

        //右上方
        for (int r = row - 1, c = col + 1; r >= 0 && c < size; r--,c++){
            if (board[r][c] == 1){
                return true;
            }
        }
        return false;
    }
}
